package com.shuo.dsa.niuke;

import java.util.ArrayList;
import java.util.List;

/**
 * 只包含质因子2、3和5的数称作丑数, 求按从小到大的顺序的第N个丑数
 *
 * 1 0 0
 * 1 1 0
 * 2 1 0
 * 2 1 1
 * 3 1 1
 * 3 2 1
 */
public class UglyNumber {
    public int GetUglyNumber_Solution(int index) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        // i是记录上次我最小的index
        int i2 = 0, i3 = 0, i5 = 0;
        while (list.size() < index) {
            int n2 = list.get(i2) * 2;
            int n3 = list.get(i3) * 3;
            int n5 = list.get(i5) * 5;
            int min = min(n2, n3, n5);
            list.add(min);
            if (min == n2) i2++;
            if (min == n3) i3++;
            if (min == n5) i5++;
        }
        return list.get(list.size() - 1);
    }

    private int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

    public static void main(String[] args) {
        new UglyNumber().GetUglyNumber_Solution(7);
    }
}
